|
In computer science, locality of reference, also known as the principle of locality, is a phenomenon describing the same value, or related storage locations, being frequently accessed. There are two basic types of reference locality temporal and spatial locality. Temporal locality refers to the reuse of specific data, and/or resources, within a relatively small time duration. Spatial locality refers to the use of data elements within relatively close storage locations. Sequential locality, a special case of spatial locality, occurs when data elements are arranged and accessed linearly, such as, traversing the elements in a one-dimensional array. Locality is merely one type of predictable behavior that occurs in computer systems. Systems that exhibit strong ''locality of reference'' are great candidates for performance optimization through the use of techniques such as the cache, instruction prefetch technology for memory, or the advanced branch predictor at the pipelining of processors. == Types of locality == There are several different types of locality of reference: ; Temporal locality : If at one point in time a particular memory location is referenced, then it is likely that the same location will be referenced again in the near future. There is a temporal proximity between the adjacent references to the same memory location. In this case it is common to make efforts to store a copy of the referenced data in special memory storage, which can be accessed faster. Temporal locality is a special case of spatial locality, namely when the prospective location is identical to the present location. ; Spatial locality : If a particular memory location is referenced at a particular time, then it is likely that nearby memory locations will be referenced in the near future. In this case it is common to attempt to guess the size and shape of the area around the current reference for which it is worthwhile to prepare faster access. ; Branch locality : If there are only a few possible alternatives for the prospective part of the path in the ''spatial-temporal coordinate space.'' This is the case when an instruction loop has a simple structure, or the possible outcome of a small system of conditional branching instructions is restricted to a small set of possibilities. Branch locality is typically not a spatial locality since the few possibilities can be located far away from each other. ; Equidistant locality : It is halfway between the spatial locality and the branch locality. Consider a loop accessing locations in an equidistant pattern, i.e. the path in the ''spatial-temporal coordinate space'' is a dotted line. In this case, a simple linear function can predict which location will be accessed in the near future. In order to benefit from the very frequently occurring ''temporal'' and ''spatial'' kind of locality, most of the information storage systems are hierarchical; see below. The ''equidistant'' locality is usually supported by the diverse nontrivial increment instructions of the processors. For the case of ''branch'' locality, the contemporary processors have sophisticated branch predictors, and on the basis of this prediction the memory manager of the processor tries to collect and preprocess the data of the plausible alternatives. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Locality of reference」の詳細全文を読む スポンサード リンク
|